πŸ‘©β€πŸ’» 67260. 동꡴ νƒν—˜

@Seongukbaek Posted April 30, 2022 Β· Updated April 30, 2022 Β· 3 min read

문제

Programmers - 동꡴ νƒν—˜

πŸ“ Logic

private void dfs() { Stack<Integer> stack = new Stack<>(); stack.push(0); visited[0] = true; for (int next : adjList.get(0)) stack.push(next); while(!stack.empty()) { int now = stack.pop(); if (visited[now]) continue; // before 정보λ₯Ό μ—…λ°μ΄νŠΈν•˜μ§€ μ•ŠλŠ” 방듀은 λͺ¨λ‘ 0번 방이 μš°μ„  λ°©λ¬Έλ˜λŠ” 경우 if (!visited[before[now]]) { after[before[now]] = now; continue; } visited[now] = true; for (int next : adjList.get(now)) if (!visited[next]) stack.push(next); stack.push(after[now]); } }
  • Stack을 μ΄μš©ν•œ DFSλ₯Ό μˆ˜ν–‰ν•œλ‹€.
  • 0번 λ°©μ—μ„œ 갈 수 μžˆλŠ” 방듀을 stack에 λ„£λŠ”λ‹€.
  • λ°©λ¬Έν•˜μ§€ μ•Šμ€ 방에 λŒ€ν•΄,

    • μš°μ„  λ°©λ¬Έν•΄μ•Ό ν•˜λŠ” 방을 λ°©λ¬Έν•˜μ§€ μ•Šμ€ 경우, 이후 λ°©λ¬Έν•΄μ•Ό ν•˜λŠ” 방듀을 μ €μž₯ν•˜λŠ” after 에 ν˜„μž¬ 방을 μ €μž₯ν•œλ‹€.
    • λ°©λ¬Έν•œ 경우, ν˜„μž¬ 방의 λ°©λ¬Έ μ—¬λΆ€λ₯Ό μ΅œμ‹ ν™”ν•˜κ³ , ν˜„μž¬ λ°©μ—μ„œ 갈 수 μžˆλŠ” 방듀을 stack에 λ„£λŠ”λ‹€.
  • 이후 ν˜„μž¬ λ°© 이후에 λ°©λ¬Έν•΄μ•Ό ν•˜λŠ” λ°©(after[now])을 stack에 λ„£κ³ , λ°˜λ³΅ν•œλ‹€.

πŸ“„ CODE

μ½”λ“œ 보기/μ ‘κΈ°πŸ’«
import java.util.*; class Solution { boolean[] visited; int[] before; int[] after; ArrayList<ArrayList<Integer>> adjList = new ArrayList<>(); public boolean solution(int n, int[][] path, int[][] order) { visited = new boolean[n]; before = new int[n]; after = new int[n]; // λ°©λ¬Έ μš°μ„ μˆœμœ„ μ €μž₯ for (int[] or : order) before[or[1]] = or[0]; for (int i = 0; i < n; i++) adjList.add(new ArrayList<>()); // 인접 리슀트 생성 for (int[] p : path) { adjList.get(p[0]).add(p[1]); adjList.get(p[1]).add(p[0]); } // 0보닀 λ¨Όμ € λ°©λ¬Έν•΄μ•Ό ν•˜λŠ” 방이 μžˆλ‹€λ©΄ λ°”λ‘œ false if (before[0] != 0) return false; dfs(); // λͺ¨λ“  λ°©λ¬Έ ν›„, λ°©λ¬Έν•˜μ§€ μ•Šμ€ 방이 μžˆλ‹€λ©΄ false for (int i = 0; i < n; i++) if (!visited[i]) return false; return true; } private void dfs() { Stack<Integer> stack = new Stack<>(); stack.push(0); visited[0] = true; for (int next : adjList.get(0)) stack.push(next); while(!stack.empty()) { int now = stack.pop(); if (visited[now]) continue; if (!visited[before[now]]) { after[before[now]] = now; continue; } visited[now] = true; for (int next : adjList.get(now)) if (!visited[next]) stack.push(next); stack.push(after[now]); } } }

✏️ Review

  • μœ„μƒ μ •λ ¬ μ•Œκ³ λ¦¬μ¦˜μ„ λ– μ˜¬λ Έμ—ˆλŠ”λ°, λ°©λ¬Έν–ˆλ˜ 방도 λ‹€μ‹œ λ°©λ¬Έν•΄μ•Όν•˜λŠ” κ²½μš°κ°€ μžˆμ„ 수 μžˆμ–΄, μ˜λ―Έκ°€ μ—†λ‹€κ³  νŒλ‹¨ν–ˆλ‹€.
  • μ—­μ‹œλ‚˜ λ§ˆμ§€λ§‰ λ¬Έμ œλ‹΅κ²Œ, λ‚œμ΄λ„κ°€ λ†’μ•˜λ‹€. 인턴 μ½”ν…Œ 5솔은 그림의 λ–‘μ΄λΌλŠ” 생각이 λ“€μ—ˆλ‹€ ..
@Seongukbaek
배우고 μ •λ¦¬ν•˜κ³  κ³΅μœ ν•˜λŠ” λŒ€ν•™μƒ λ°±μ„±μš±μž…λ‹ˆλ‹€ πŸ˜€